package leetcode_day._2021._202111;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/11/17 10:27
 * 最大单词长度乘积
 * 给定一个字符串数组 words，找到 length(word[i]) * length(word[j]) 的最大值，并且这两个单词不含有公共字母。
 * 你可以认为每个单词只包含小写字母。如果不存在这样的两个单词，返回 0。
 * 算法：位运算 + 模拟
 * 将字符串用整型的低 26 位来表示
 * 得到的数代表该字符串中有哪些字符
 */
public class _17_318 {

    /**
     * 执行用时：10ms；内存消耗：38.5MB
     * @param words
     * @return
     */
    public int maxProduct(String[] words) {
        int len = words.length, idx = 0;
        int[] masks = new int[len];
        for (String s : words) {
            int mask = 0;
            for (char c : s.toCharArray()) mask |= (1 << (c - 'a'));
            masks[idx++] = mask;
        }
        int ans = 0;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if ((masks[i] & masks[j]) == 0)
                    ans = Math.max(ans, words[i].length() * words[j].length());
            }
        }
        return ans;
    }

    /**
     * 上面方法中可能会记录一些重复的字符串，即两个字符串所拥有的字符种类是一样的
     * 也就是 mask 值相等
     * 执行用时：24ms；内存消耗：38.7MB
     * @param words
     * @return
     */
    public int maxProduct_perfect(String[] words) {
        Map<Integer, Integer> map = new HashMap<>(16);
        for (String word : words) {
            int mask = 0;
            int len = word.length();
            for (char c : word.toCharArray()) mask |= (1 << (c - 'a'));
            if (!map.containsKey(mask) || map.get(mask) < len) map.put(mask, len);
        }
        final Set<Integer> keys = map.keySet();
        int ans = 0;
        for (Integer a : keys) {
            for (Integer b : keys) if ((a & b) == 0) ans = Math.max(ans, map.get(a) * map.get(b));
        }
        return ans;
    }

}
